public class Solution1155 {
    public int numRollsToTarget(int n, int k, int target) {
        int[][] f=new int[n][target+1];
        for (int i=1;i<=Math.min(k,target);i++){
            f[0][i]=1;
        }
        for (int i=1;i<n;i++){
            for (int j=i+1;j<=Math.min(target,(i+1)*k);j++){
                for (int p=1;p<=k;p++){
                    if (j-p>0){
                        f[i][j]=(f[i][j]+f[i-1][j-p])%1000000007;
                    }
                }
            }
        }
        return f[n-1][target];
    }

    public static void main(String[] args) {
        System.out.println(new Solution1155().numRollsToTarget(30,30,500));
    }
}
